package com.xhh.learning.record.algorithm.sort;

/**
 * 类名： HeapSort
 * 描述：
 * 公司： 北京海鑫科金高科技股份有限公司
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/4/25 15:00
 * 最后修改时间:  2019/4/25 15:00
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] a = {0,5,8,1,6,3,2,9,4,7};

        heapSort(a);

        for (int i : a) {
            System.out.print(i+",");
        }

    }

    private static void heapSort(int[] a){
        int n = a.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            adjustHeap(a, i, n);
        }

        for (int i = n - 1; i > 0; i--) {
            swap(a, i, 0);
            adjustHeap(a, 0, i);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void adjustHeap(int[] a, int i, int n) {
        int temp = a[i];
        for (int k = 2 * i + 1; k < n; k = 2 * i + 1) {
            if (k+1<n && a[k] < a[k + 1]) {
                k++;
            }

            if (temp < a[k]) {
                a[i] = a[k];
                i = k;
            } else {
                break;
            }
        }
        a[i] = temp;
    }
}
